package daily;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2023-12-30
 * @Author Jonathan
 * todo 用Java实现一遍
 */
public class LRUCache {
    static class LRUNode {
        private Integer key;
        private Integer value;
        private LRUNode next;
        private LRUNode prev;

        public LRUNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }

        public LRUNode() {
        }
    }

    // dummyHead
    private LRUNode head;
    // dummyTail
    private LRUNode tail;
    private int capacity;
    private Map<Integer, LRUNode> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new LRUNode();
        tail = new LRUNode();
        head.next = tail;
        tail.prev = head;
        cache = new HashMap<>();
    }


    public void put(Integer key, Integer value) {
        if (cache.containsKey(key)) {
            LRUNode node = cache.get(key);
            removeNode(node);
        }
        LRUNode node = new LRUNode(key, value);
        cache.put(key, node);
        addNode(node);
        // 开始进行淘汰判断，即超过capacity上限，需要从头部进行剔除
        if (cache.size() > capacity) {
            // 在头部移除 尾部添加
            LRUNode evictedNode = head.next;
            removeNode(evictedNode);
            cache.remove(evictedNode.key);
        }
    }


    public Integer get(Integer key) {
        if (cache.containsKey(key)) {
            LRUNode node = cache.get(key);
            // 链表中移除
            removeNode(node);
            // 添加到链表尾部
            addNode(node);
            return node.value;
        }
        return null;
    }

    private void addNode(LRUNode node) {
        LRUNode prev = tail.prev;
        prev.next = node;
        node.prev = prev;
        node.next = tail;
        tail.prev = node;
    }


    private void removeNode(LRUNode node) {
        LRUNode prev = node.prev;
        LRUNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }


    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        System.out.println(lruCache.get(1));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(2));
    }
}
